public class Thirteen {

    public int movingCount(int m, int n, int k) {
        int[][] board = new int[m][n];
        dfs(board,m,n,k,0,0);
        int ans =0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (board[i][j]==1)
                    ans++;
            }
        }
        return  ans;

    }

    public void dfs(int[][] board,int m,int n,int k,int i,int j){
        if (i<0||i>=m||j<0||j>=n||!check(i,j,k)||board[i][j]==1){
            return;
        }
        board[i][j] = 1;
        dfs(board,m,n,k,i-1,j);
        dfs(board,m,n,k,i+1,j);
        dfs(board,m,n,k,i,j-1);
        dfs(board,m,n,k,i,j+1);
    }

    public boolean check(int i,int j,int k){
        int check = 0;
        while (i>0||j>0){
            check += i%10;
            check += j%10;
            i = i/10;
            j = j/10;
        }
        return check<=k?true:false;
    }
}
